package _08_DFS_BFS;

import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.*;

public class _130_被围绕的区域 {

    public static void main(String[] args) {

        char[][] ins = new char[][]{
                {O, X, X, O, X},
                {X, O, O, X, O},
                {X, O, X, O, X},
                {O, X, O, O, O},
                {X, X, O, X, O},
        };

        _130_被围绕的区域 v = new _130_被围绕的区域();
        v.solve(ins);

        for (char[] in : ins) {
            System.out.println(Arrays.toString(in));
        }
    }

    private static final char X = 'X';

    private static final char O = 'O';

    private int rowEnd;

    private int colEnd;

    private int[][] vertex = new int[][]{
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1},
    };

    public void solve(char[][] board) {
        rowEnd = board.length - 1;
        colEnd = board[0].length - 1;
        // 存放被访问过的元素
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int row = 1; row < rowEnd; row++) {
            for (int col = 1; col < colEnd; col++) {
                if (board[row][col] == O && !visited[row][col]) {
                    bfs(board, row, col, visited);
                }
            }
        }
    }

    public void bfs(char[][] board, int row, int col, boolean[][] visited) {
        // 将所有遍历到的元素存入集合中
        boolean isSuccess = true;
        List<int[]> list = new ArrayList<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{row, col});
        list.add(new int[]{row, col});
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int[] ints : vertex) {
                int newRow = node[0] + ints[0];
                int newCol = node[1] + ints[1];
                // 判断临界条件
                if (!visited[newRow][newCol] && newRow >= 1 && newRow < rowEnd && newCol >= 1 && newCol < colEnd && board[newRow][newCol] == O) {
                    // 符合被包围的条件
                    list.add(new int[]{newRow, newCol});
                    queue.offer(new int[]{newRow, newCol});
                    visited[newRow][newCol] = true;
                }
                if ((newRow == 0 || newRow == rowEnd || newCol == 0 || newCol == colEnd) && board[newRow][newCol] == O) {
                    isSuccess = false;
                }
            }
        }
        // 更新元素
        if (isSuccess) {
            for (int[] ints : list) {
                board[ints[0]][ints[1]] = X;
            }
        }
    }

}
